package com.yubest;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Stack;

/**
 * 给你一个由若干括号和字母组成的字符串 s ，删除最小数量的无效括号，使得输入的字符串有效。
 *
 * 返回所有可能的结果。答案可以按 任意顺序 返回。
 *
 *
 *
 * 示例 1：
 *
 * 输入：s = "()())()"
 * 输出：["(())()","()()()"]
 * 示例 2：
 *
 * 输入：s = "(a)())()"
 * 输出：["(a())()","(a)()()"]
 * 示例 3：
 *
 * 输入：s = ")("
 * 输出：[""]
 *
 *
 * 提示：
 *
 * 1 <= s.length <= 25
 * s 由小写英文字母以及括号 '(' 和 ')' 组成
 * s 中至多含 20 个括号
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/remove-invalid-parentheses
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @Author hweiyu
 * @Description
 * @Date 2021/10/27 14:01
 */
public class P0301 {

    public static void main(String[] args) {

        //todo 未完成

        System.out.println(new Solution301().removeInvalidParentheses("()())()"));

        System.out.println(new Solution301().removeInvalidParentheses("(a)())()"));

        System.out.println(new Solution301().removeInvalidParentheses(")("));

        System.out.println(new Solution301().removeInvalidParentheses("x("));

        System.out.println(new Solution301().removeInvalidParentheses("(()"));

        System.out.println(new Solution301().removeInvalidParentheses(")()("));

        System.out.println(new Solution301().removeInvalidParentheses(")d))"));

        //["k()","(k)"]
        System.out.println(new Solution301().removeInvalidParentheses("(((k()(("));

    }
}

class Solution301 {

    /**
     * 思路：先找到异常的括号，然后删掉异常括号前面的不相连的正确括号
     * @param s
     * @return
     */
//    public List<String> removeInvalidParentheses(String s) {
//        List<Integer> errorIndex = new ArrayList<>(s.length());
//        Stack<Item301> stack = new Stack<>();
//        for (int i = 0; i < s.length(); i++) {
//            if ('(' == s.charAt(i)) {
//                stack.push(new Item301('(', i));
//            } else if (')' == s.charAt(i)) {
//                if (!stack.isEmpty() && stack.peek().getCharacter() == '(') {
//                    stack.pop();
//                } else {
//                    errorIndex.add(i);
//                }
//            }
//        }
//        while (!stack.isEmpty()) {
//            errorIndex.add(stack.pop().getIndex());
//        }
//        Collections.sort(errorIndex);
//        List<String> r = new ArrayList<>();
//        r.add(s);
//        List<String> t;
//        int offset = 0;
//        boolean isDel = false;
//        for (Integer index : errorIndex) {
//            index = index - offset;
//            t = new ArrayList<>();
//            for (String aR : r) {
//                if (index == 0) {
//                    t.add(aR.substring(1));
//                    continue;
//                }
//                if ('(' == aR.charAt(index)) {
//                    t.add(aR.substring(0, index) + aR.substring(index + 1));
//                    continue;
//                }
//                for (int j = 0; j < index; j++) {
//                    if (aR.charAt(j) == aR.charAt(index)) {
//                        t.add(aR.substring(0, j) + aR.substring(j + 1));
//                        isDel = true;
//                    }
//                }
//                if (!isDel) {
//                    t.add(aR.substring(0, index) + aR.substring(index + 1));
//                }
//            }
//            r = t;
//            offset++;
//        }
//        if (r.isEmpty()) {
//            r.add("");
//        }
//        return r;
//    }

    public List<String> removeInvalidParentheses(String s) {
        //先处理右括号 )
        List<Integer> errorIndex = new ArrayList<>(s.length());
        Stack<Item301> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            if ('(' == s.charAt(i)) {
                stack.push(new Item301('(', i));
            } else if (')' == s.charAt(i)) {
                if (!stack.isEmpty() && stack.peek().getCharacter() == '(') {
                    stack.pop();
                } else {
                    errorIndex.add(i);
                }
            }
        }
        List<String> right = new ArrayList<>();
        if (errorIndex.size() > 0) {
            right.add(s);
        }
        List<String> t;
        int offset = 0;
        boolean isDel = false;
        for (Integer index : errorIndex) {
            index = index - offset;
            t = new ArrayList<>();
            for (String aR : right) {
                if (index == 0) {
                    t.add(aR.substring(1));
                    continue;
                }
                for (int j = 0; j < index; j++) {
                    if (aR.charAt(j) == aR.charAt(index)) {
                        t.add(aR.substring(0, j) + aR.substring(j + 1));
                        isDel = true;
                    }
                }
                if (!isDel) {
                    t.add(aR.substring(0, index) + aR.substring(index + 1));
                }
            }
            right = t;
            offset++;
        }

        //处理左括号 (
        errorIndex.clear();
        stack.clear();
        for (int i = s.length() - 1; i >= 0; i--) {
            if (')' == s.charAt(i)) {
                stack.push(new Item301(')', i));
            } else if ('(' == s.charAt(i)) {
                if (!stack.isEmpty() && stack.peek().getCharacter() == ')') {
                    stack.pop();
                } else {
                    errorIndex.add(i);
                }
            }
        }
        List<String> left = new ArrayList<>();
        if (errorIndex.size() > 0) {
            left.add(s);
        }
        for (Integer index : errorIndex) {
            t = new ArrayList<>();
            for (String aR : left) {
                if (index == aR.length() - 1) {
                    t.add(aR.substring(0, aR.length() - 1));
                    continue;
                }
                for (int j = aR.length() - 1; j > index; j--) {
                    if (aR.charAt(j) == aR.charAt(index)) {
                        t.add(aR.substring(0, j) + aR.substring(j + 1));
                        isDel = true;
                    }
                }
                if (!isDel) {
                    t.add(aR.substring(0, index) + aR.substring(index + 1));
                }
            }
            left = t;
        }
        right.addAll(left);
        return right;
    }

}

class Item301 {

    private Character character;

    private Integer index;

    public Item301(Character character, Integer index) {
        this.character = character;
        this.index = index;
    }

    public Character getCharacter() {
        return character;
    }

    public Integer getIndex() {
        return index;
    }
}
